{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树剪枝"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pruneTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树剪枝"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树 <strong>根节点</strong>&nbsp;<code>root</code>&nbsp;，树的每个节点的值要么是 <code>0</code>，要么是 <code>1</code>。请剪除该二叉树中所有节点的值为 <code>0</code> 的子树。</p>\n",
    "\n",
    "<p>节点 <code>node</code> 的子树为&nbsp;<code>node</code> 本身，以及所有 <code>node</code>&nbsp;的后代。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1,null,0,0,1]\n",
    "<strong>输出: </strong>[1,null,0,null,1] \n",
    "<strong>解释:</strong> \n",
    "只有红色节点满足条件&ldquo;所有不包含 1 的子树&rdquo;。\n",
    "右图为返回的答案。\n",
    "\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png\" style=\"width:450px\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1,0,1,0,0,0,1]\n",
    "<strong>输出: </strong>[1,null,1,null,1]\n",
    "<strong>解释:</strong> \n",
    "\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png\" style=\"width:450px\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> [1,1,0,1,1,0,1,0]\n",
    "<strong>输出: </strong>[1,1,0,1,1,null,1]\n",
    "<strong>解释:</strong> \n",
    "\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png\" style=\"width:450px\" />\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[1,200]</code></li>\n",
    "\t<li>二叉树节点的值只会是 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 814&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/binary-tree-pruning/\">https://leetcode-cn.com/problems/binary-tree-pruning/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [pOCWxh](https://leetcode.cn/problems/pOCWxh/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [pOCWxh](https://leetcode.cn/problems/pOCWxh/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            total = root.val\n",
    "            if root.left:\n",
    "                if recur(root.left) == 0:\n",
    "                    root.left = None\n",
    "                else:\n",
    "                    total += recur(root.left)\n",
    "            if root.right:\n",
    "                if recur(root.right) == 0:\n",
    "                    root.right = None\n",
    "                else:\n",
    "                    total += recur(root.right)\n",
    "            if total == 0:\n",
    "                root = None\n",
    "            return total\n",
    "        if root.val == 0 and recur(root.left) == 0 and recur(root.right) == 0:\n",
    "            return None\n",
    "        recur(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def f(root):\n",
    "            if not root:return \n",
    "            root.left = f(root.left)\n",
    "            root.right = f(root.right)\n",
    "            if root.val == 0 and not root.left and not root.right:\n",
    "                return\n",
    "            return root\n",
    "        return f(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "\n",
    "        def dfs(node):\n",
    "            lf, rf = None, None\n",
    "            if node.left:\n",
    "                lf = dfs(node.left)\n",
    "            if node.right:\n",
    "                rf = dfs(node.right)\n",
    "\n",
    "            if lf is None:\n",
    "                node.left = None\n",
    "\n",
    "            if rf is None:\n",
    "                node.right = None\n",
    "            \n",
    "            if lf is None and rf is None and node.val == 0:\n",
    "                return None\n",
    "            else:\n",
    "                return 1\n",
    "        \n",
    "        dfs(root)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(0,root)\n",
    "\n",
    "        def f(node):\n",
    "            tmp = node.val\n",
    "            if node.left:\n",
    "                sum_left = f(node.left)\n",
    "                if sum_left:\n",
    "                    tmp += sum_left\n",
    "                else:\n",
    "                    node.left = None\n",
    "            if node.right:\n",
    "                sum_right = f(node.right)\n",
    "                if sum_right:\n",
    "                    tmp += sum_right\n",
    "                else:\n",
    "                    node.right = None\n",
    "            return tmp\n",
    "        f(dummy)\n",
    "        return dummy.left\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def f(root):\n",
    "            if not root:return\n",
    "            root.left = f(root.left)\n",
    "            root.right = f(root.right)\n",
    "            if root.val == 0 and not root.left and not root.right:\n",
    "                root = None\n",
    "            return root\n",
    "        return f(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            v1=dfs(node.left)\n",
    "            v2=dfs(node.right)\n",
    "            if v1==None:\n",
    "                node.left=None\n",
    "            if v2==None:\n",
    "                node.right=None\n",
    "            # if v1==0 and v2==0 and node.val==0:\n",
    "            #     return 0\n",
    "            # else:\n",
    "            if v1 is None and v2 is None and node.val==0:\n",
    "                return None\n",
    "            return node\n",
    "        \n",
    "        res = dfs(root)\n",
    "        # if root.val==0 and root.left==None and root.right==None: return None\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            root = None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root: return \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def isAll0(p):\n",
    "            if p.val !=0: return False\n",
    "            if p.left:\n",
    "                if not isAll0(p.left): return False\n",
    "            if p.right:\n",
    "                if not isAll0(p.right): return False\n",
    "            return True\n",
    "        def bl(p):\n",
    "            if p.left and isAll0(p.left):\n",
    "                p.left = None\n",
    "            if p.right and isAll0(p.right):\n",
    "                p.right= None\n",
    "            if p.left:\n",
    "                bl(p.left)\n",
    "            if p.right:\n",
    "                bl(p.right)\n",
    "        if root is None: return None\n",
    "        if isAll0(root): return None\n",
    "        \n",
    "        bl(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        return root if root.val == 1 or root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            \n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            if not left and not right and root.val == 0:\n",
    "                return None\n",
    "            else:\n",
    "                return root\n",
    "\n",
    "        newHead = TreeNode(val = 1, left = root)\n",
    "        dfs(newHead)\n",
    "        return newHead.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root==None:\n",
    "            return None\n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right=self.pruneTree(root.right)\n",
    "        if root.val==0 and root.left==None and root.right==None:\n",
    "            root=None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "\n",
    "        def prune(node: Optional[TreeNode]) -> int:\n",
    "            leftVal, rightVal = 0, 0\n",
    "            if node.left:\n",
    "                leftVal = prune(node.left)\n",
    "                if leftVal == 0:\n",
    "                    node.left = None\n",
    "                \n",
    "            if node.right:\n",
    "                rightVal = prune(node.right)\n",
    "                if rightVal == 0:\n",
    "                    node.right = None\n",
    "\n",
    "            return node.val + leftVal + rightVal\n",
    "        \n",
    "        val = prune(root)\n",
    "\n",
    "        if val == 0:\n",
    "            return None\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        # DFS 遍历\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        # 剪枝\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pruneTree(self, root):\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.val == 0 and not root.left and not root.right:\n",
    "            return None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "\n",
    "        def remove(root, parent, is_left):\n",
    "            if root.left: remove(root.left, root, True)\n",
    "            if root.right: remove(root.right, root, False)\n",
    "\n",
    "            if (not root.left) and (not root.right) and (root.val == 0):\n",
    "                if is_left:\n",
    "                    parent.left = None\n",
    "                else:\n",
    "                    parent.right = None\n",
    "            return\n",
    "            \n",
    "        if root.left: remove(root.left, root, True)\n",
    "        if root.right: remove(root.right, root, False)\n",
    "\n",
    "        if (not root.left) and (not root.right) and (root.val == 0):\n",
    "            root = None\n",
    "        return root\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        else:\n",
    "            l=self.pruneTree(root.left)\n",
    "            r=self.pruneTree(root.right)\n",
    "            if root.val==0 and not l and not r:\n",
    "                return None\n",
    "            else:\n",
    "                root.left=l\n",
    "                root.right=r\n",
    "                return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        res=self.search(root)\n",
    "        if res:\n",
    "            return None\n",
    "        else:\n",
    "            return root\n",
    "\n",
    "    def search(self, node):\n",
    "        if not node:\n",
    "            return False\n",
    "        left=self.search(node.left)\n",
    "        if left:\n",
    "            node.left=None\n",
    "        right=self.search(node.right)\n",
    "        if right:\n",
    "            node.right=None\n",
    "        if not node.left and not node.right:\n",
    "            if node.val==0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, node: TreeNode) -> TreeNode:\n",
    "        if not node:\n",
    "            return node\n",
    "        node.left = self.pruneTree(node.left)\n",
    "        node.right = self.pruneTree(node.right)\n",
    "        if node.val == 0:\n",
    "            if not node.left and not node.right:\n",
    "                return None\n",
    "        \n",
    "        return node\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None \n",
    "            \n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val == 0 and not node.left and not node.right:\n",
    "                return None \n",
    "            \n",
    "            return node \n",
    "        \n",
    "        return dfs(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        if not root.left and not root.right:\n",
    "            if root.val == 0:\n",
    "                return None\n",
    "            else :\n",
    "                return root\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        # root.left = self.pruneTree(root.left)\n",
    "        # root.right = self.pruneTree(root.right)\n",
    "        # if not root.left and not root.right and root.val == 0: \n",
    "        #     return None\n",
    "        # return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return True\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if left:\n",
    "                node.left = None\n",
    "            if right:\n",
    "                node.right = None\n",
    "            if node.val == 1:\n",
    "                return False\n",
    "            else:\n",
    "                return (left and right)\n",
    "        \n",
    "        ans = dfs(root)\n",
    "        if ans:\n",
    "            return None\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            left_sum = helper(root.left)\n",
    "            right_sum = helper(root.right)\n",
    "            if left_sum == 0:\n",
    "                root.left = None\n",
    "            if right_sum == 0:\n",
    "                root.right = None\n",
    "            return root.val + left_sum + right_sum\n",
    "        \n",
    "        ret = helper(root)\n",
    "        if ret == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(cnt:TreeNode):\n",
    "            left = right = -1\n",
    "            if cnt.left is not None:\n",
    "                left = dfs(cnt.left)\n",
    "            if cnt.right is not None:\n",
    "                right = dfs(cnt.right)\n",
    "            if left == 0:\n",
    "                cnt.left = None\n",
    "            if right == 0:\n",
    "                cnt.right = None\n",
    "            if left == 1 or right == 1:\n",
    "                return 1\n",
    "            if cnt.val == 1:\n",
    "                return 1\n",
    "            return 0\n",
    "        r = dfs(root)\n",
    "        if r == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            if root.val == 0:\n",
    "                if root.left and root.right:\n",
    "                    a, b = 0, 0\n",
    "                    if dfs(root.left) == 0:\n",
    "                        a = 1\n",
    "                    if dfs(root.right) == 0:\n",
    "                        b = 1\n",
    "                    if a and b:\n",
    "                        root.val = 2\n",
    "                        return 0\n",
    "                    return 1\n",
    "                elif root.left:\n",
    "                    if dfs(root.left) == 0:\n",
    "                        root.val=2\n",
    "                        return 0\n",
    "                    return 1\n",
    "                elif root.right:\n",
    "                    if dfs(root.right) == 0:\n",
    "                        root.val = 2\n",
    "                        return 0\n",
    "                    return 1\n",
    "                else:\n",
    "                    root.val = 2\n",
    "                    return 0\n",
    "            else:\n",
    "                if root.left:\n",
    "                    dfs(root.left) \n",
    "                if root.right:\n",
    "                    dfs(root.right)\n",
    "                return 1 \n",
    "        dfs(root)\n",
    "        if root.val == 2:\n",
    "            return None\n",
    "        def dfs1(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left:\n",
    "                if root.left.val == 2:\n",
    "                    root.left = None\n",
    "                else:\n",
    "                    dfs1(root.left)\n",
    "            if root.right:\n",
    "                if root.right.val == 2:\n",
    "                    root.right = None\n",
    "                else:\n",
    "                    dfs1(root.right)\n",
    "        dfs1(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = recur(root.left)\n",
    "            root.right = recur(root.right)\n",
    "            if root.val == 0 and not root.left and not root.right:\n",
    "                return None\n",
    "            return root\n",
    "        return recur(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for a binary tree node.\n",
    "# # class TreeNode:\n",
    "# #     def __init__(self, val=0, left=None, right=None):\n",
    "# #         self.val = val\n",
    "# #         self.left = left\n",
    "# #         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        # 搜索，并且返回是否为全0子树\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root \n",
    "\n",
    "# class Solution:\n",
    "#     def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "#         if root is None:\n",
    "#             return None\n",
    "#         root.left = self.pruneTree(root.left)\n",
    "#         root.right = self.pruneTree(root.right)\n",
    "#         if root.left is None and root.right is None and root.val == 0:\n",
    "#             return None\n",
    "#         return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        def dfs(node):\n",
    "            if node==None:\n",
    "                return 0\n",
    "            v1=dfs(node.left)\n",
    "            v2=dfs(node.right)\n",
    "            if v1==0:\n",
    "                node.left=None\n",
    "            if v2==0:\n",
    "                node.right=None\n",
    "            # if v1==0 and v2==0 and node.val==0:\n",
    "            #     return 0\n",
    "            # else:\n",
    "            return v1+v2+node.val\n",
    "        \n",
    "        dfs(root)\n",
    "        if root.val==0 and root.left==None and root.right==None: return None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root == None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left == None and root.right == None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def traversal(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = traversal(root.left)\n",
    "            root.right = traversal(root.right) \n",
    "            if root.val == 0 and not root.left and not root.right:\n",
    "                return None\n",
    "            return root\n",
    "        root = traversal(root)\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(o: TreeNode) -> TreeNode:\n",
    "            if not o:\n",
    "                return None\n",
    "            o.right = dfs(o.right)\n",
    "            o.left = dfs(o.left)\n",
    "            if not o.right and not o.left and not o.val:\n",
    "                return None\n",
    "            return o\n",
    "\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val==0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if (not root.left) and (not root.right) and (root.val == 0):\n",
    "            return None\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def contains_one(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            left_contains_one = contains_one(node.left)\n",
    "            right_contains_one = contains_one(node.right)\n",
    "            \n",
    "            if not left_contains_one:\n",
    "                node.left = None\n",
    "            if not right_contains_one:\n",
    "                node.right = None\n",
    "            \n",
    "            return node.val == 1 or left_contains_one or right_contains_one\n",
    "        \n",
    "        return root if contains_one(root) else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.val == 0 and root.left == None and root.right == None:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        # 后序位置剪枝\n",
    "        if root.val == 0 and root.left is None and root.right is None:\n",
    "            return None\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left or root.right:\n",
    "            return root\n",
    "        else:\n",
    "            return None if root.val == 0 else root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            l, r = dfs(root.left), dfs(root.right)\n",
    "            if not l: root.left = None\n",
    "            if not r: root.right = None\n",
    "            return l + r + root.val\n",
    "\n",
    "        return root if dfs(root) else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right =self.pruneTree(root.right)\n",
    "        if root.left is root.right and root.val ==0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def dfs(node: TreeNode):\n",
    "    if node == None:\n",
    "        return\n",
    "    \n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root == None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        # 左右节点都为空且节点的值为1时，将该节点置为空且返回空节点\n",
    "        if root.left == None and root.right == None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            root = None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val ==0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return \n",
    "        root.left=self.pruneTree(root.left)\n",
    "        root.right=self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val==0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root == None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val == 0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left is None and root.right is None and root.val == 0:\n",
    "            root = None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if not root.left and not root.right and root.val==0:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if  root is None:\n",
    "            return None\n",
    "        root.left =  self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        \n",
    "        if  root.left is None and root.right is None and root.val == 0:\n",
    "            return None\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def check_node(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            else:\n",
    "                left_node = check_node(node.left)\n",
    "                right_node = check_node(node.right)\n",
    "                if not left_node and not right_node:\n",
    "                    if node.val == 0:\n",
    "                        return None\n",
    "                node.left = left_node\n",
    "                node.right = right_node\n",
    "                return node\n",
    "        ret_node = check_node(root)\n",
    "        return ret_node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        #### 根据题意，后序遍历最方便，找到叶子节点,val=0 则删除\n",
    "        ### 递归法\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "        if root.left == None and root.right == None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        if root == None:\n",
    "            return None\n",
    "        \n",
    "        root.left = self.pruneTree(root.left)\n",
    "        root.right = self.pruneTree(root.right)\n",
    "\n",
    "        if root.left == None and root.right == None and root.val == 0:\n",
    "            return None\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pruneTree(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if not left: # left == 0\n",
    "                node.left = None\n",
    "            if not right:# right == 0\n",
    "                node.right = None\n",
    "            return node.val + left + right\n",
    "        ans = dfs(root)\n",
    "        if not ans: # ans == 0\n",
    "            return None\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
